//
// Created by root on 2/18/18.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
#include "stack.h"
#include "../base/cmemory.h"

GraphNode *alloc_graph_node() {
    GraphNode *node = (GraphNode *) sys_malloc(sizeof(GraphNode));
    return node;
}

Graph *init_graph() {
    Graph *g = (Graph *) sys_malloc(sizeof(Graph));
    g->vertexCount = 0;
    g->edgeCount = 0;
    g->nodes = init_queue();
    return g;
}

void add_vertex(Graph *g, char *id, void *element) {
    GraphNode *node = alloc_graph_node();
    node->id = id;
    node->element = element;
    node->inDegree = 0;
    node->tempInDegree = 0;
    node->adjList = init_queue();
    enqueue(g->nodes, node);
    g->vertexCount++;
}

static GraphNode *find_graph_node_by_id(Queue *queue, char *id) {
    GraphNode *graphNode = NULL;
    QueueNode *node = queue->head;
    while (node != NULL) {
        graphNode = (GraphNode *)(node->element);
        if (strcmp(graphNode->id, id) == 0) {
            return graphNode;
        }
        node = node->next;
    }
    return NULL;
}

void add_edge(Graph *g, char *src, char *dest) { //todo exclude duplicate
    // find dest node
    GraphNode *graphNodeDest = find_graph_node_by_id(g->nodes, dest);
    GraphNode *graphNodeSrc = find_graph_node_by_id(g->nodes, src);
    enqueue(graphNodeSrc->adjList, dest);
    graphNodeDest->inDegree++;
    graphNodeDest->tempInDegree++;
    g->edgeCount++;
}

Queue *topological_sort(Graph *g) {
    Queue *queue = init_queue();
    Stack *stack = init_stack();

    GraphNode *graphNode = NULL;
    QueueNode *queueNode = g->nodes->head;
    while (queueNode != NULL) {
        graphNode = (GraphNode *)(queueNode->element);
        if (graphNode->tempInDegree == 0) {
            push(&stack, &(graphNode->id));
        }
        queueNode = queueNode->next;
    }

    char *nodeId;
    GraphNode *tempNode = NULL;
    char *tempId;
    while (!is_stack_empty(stack)) {
        nodeId = *((char **)(pop(&stack)));
        graphNode = find_graph_node_by_id(g->nodes, nodeId);
        enqueue(queue, graphNode);

        queueNode = graphNode->adjList->head;
        while (queueNode != NULL) {
            tempId = (char *)queueNode->element;
            tempNode = find_graph_node_by_id(g->nodes, tempId);
            tempNode->tempInDegree--;
            if (tempNode->tempInDegree == 0) {
                push(&stack, &(tempNode->id));
            }
            queueNode = queueNode->next;
        }
    }
    return queue;
}
